﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//手搓一个链表

typedef struct ListNode
{ 
	int val;//储存数据
	struct ListNode* next;//存放下一个节点的指针
}SLNode;


//打印链表
void SListPrint(SLNode* s)
{
	assert(s);
	while (s)
	{
		printf("%d ", s->val);
		s = s->next;
	}
	printf("\n");
}


//删除指定元素所在节点
//struct ListNode* removeElements(struct ListNode* head, int val) {
//	struct ListNode* temp = head;
//	while (temp)
//	{
//		if(temp->val == val && temp == head)
//		 {
//			 head = head->next;
//			 free(temp);
//			 temp = head;
//		 }
//		else if (temp->next && temp->next->val == val)
//		{
//			struct ListNode* s = temp->next->next;
//			free(temp->next);
//			temp->next = s;
//			temp = temp->next;
//		}
//		else if(temp)
//			temp = temp->next;
//	}
//	return head;
//}

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* temp = NULL;
	struct ListNode* crp = head;
	while (crp)
	{
		if (crp->val == val)
		{
			if (crp == head)
			{
				head = head->next;
				free(crp);
				crp = head;
			}
			else
			{
				temp->next = crp->next;
				free(crp);
				crp = temp->next;
			}
		}
		else
		{
			temp = crp;
			crp = crp->next;
		}
	}
	return head;
}

//反转链表 n1 n2 n3
struct ListNode* reverseList(struct ListNode* head) {
	if (head == NULL)
		return NULL;
	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = head->next;
	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3)
		{
			n3 = n3->next;
		}
	}
	return n1;
}

//中间节点
struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}


//返回链表中倒数第k个节点
// 
//法一 暴力解法： 思路 先遍历一遍，由公式n-k+1得到该倒数在正数的多少位置，然后遍历到改位置，返回即可。
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//	// write code here
//	assert(pListHead);
//	int total_length = 0;
//	int x = 0;
//	struct ListNode* pL = pListHead;
//	while (pL)
//	{
//		total_length++;
//		pL = pL->next;
//	}
//	x = total_length - k + 1;
//	if (x <= 0)
//		return NULL;
//	for (int i = 1; i < x; i++)
//	{
//		pListHead = pListHead->next;
//	}
//	return pListHead;
//}

//法2 双指针 快慢针 为了得到倒数第k个，那么我们定义两个指针，一个指针指向null的时候，
//此时慢指针就指向倒数第k个，那么这中间必须就格上k-1个空，当两个指针从同一起点出发，快指针先行k步，那么中间就有k-1个空，然后一起行走即可。
//特殊情况 链表里没有数组，却还要返回 判断在for循环里面是否有空指针被引用的情况  返回倒数0 或者也是超出范围的。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
	struct ListNode* fast, * slow;
	fast = slow = pListHead;
	if (k == 0)
		return NULL;
	//fast先走k步
	for (int i = 0; i < k; i++)
	{
		//当k大于整个链表的长度
		if (fast == NULL)
			return NULL;
		fast = fast->next;
	}
	//fast到空的时候就结束
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}


//和并两个有序链表
//方法一：创建一个用来合并 返回创建的即可
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//	struct ListNode* new = NULL;
//	struct ListNode* news = (SLNode*)malloc(sizeof(SLNode));
//	assert(news);
//	new = news;
//	//如果两个都是NULL返回合并的NULL即可
//	if (list1 == NULL && list2 == NULL)
//	{
//		free(news);
//		news = NULL;
//		return NULL;
//	}
//	while (list1 || list2)
//	{
//		if (list1 && list2)
//		{
//			if (list1->val >= list2->val)
//			{
//				news->next = list2;
//				list2 = list2->next;
//			}
//			else
//			{
//				news->next = list1;
//				list1 = list1->next;
//			}
//
//
//		}
//		else if (list1)
//		{
//			news->next = list1;
//			list1 = list1->next;
//		}
//		else if (list2)
//		{
//			news->next = list2;
//			list2 = list2->next;
//		}
//		news = news->next;
//	}
//	return new->next;
//}
//方法2
//归并，从头比较 取小的尾插到新链表 此链表未带哨兵位
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//	//如果其中一个为空链表，那么只需要返回另一个链表即可
//	if (list1 == NULL)
//		return list2;
//	if (list2 == NULL)
//		return list1;
//
//	struct ListNode* head, * tail;//一个用于返回头的指针，一个用于每次改变的指针
//	head = tail = NULL;//一开始赋予空，下面当执行第一步的时候需要带上头
//
//	//当list1和list2均不为空的时候，就是两者的数据进行比较 我们将这两个比较放在一个循环里面即可
//	while (list1 && list2)
//	{
//		if (list1->val >= list2->val)
//		{
//			if (head == NULL)//第一次进入
//				head = tail = list2;
//			else//后面次进
//			{
//				tail->next = list2;
//				tail = tail->next;
//			}
//			list2 = list2->next;
//		}
//		else
//		{
//			if (head == NULL)//同理
//				head = tail = list1;
//			else
//			{
//				tail->next = list1;
//				tail = tail->next;
//			}
//			list1 = list1->next;
//		}
//	}
//
//	//当只有list2 为空的时候，后面的只需继承list1即可 tail也不需要变化了。
//	if (list1)
//	{
//		tail->next = list1;
//	}
//	//同理
//	if (list2)
//	{
//		tail->next = list2;
//	}
//
//	return head;
//}

//法2 加上哨兵位：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	struct ListNode* head, * tail;//一个用于返回头的指针，一个用于每次改变的指针
	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); //创建一个虚拟节点，数据为随机值，但是next置为NULL即可
	assert(head && tail);
	tail->next = NULL;

	//当list1和list2均不为空的时候，就是两者的数据进行比较 我们将这两个比较放在一个循环里面即可
	while (list1 && list2)
	{
		if (list1->val >= list2->val)
		{
			//哨兵位不需要判断是否第一次进了，因为始终都是尾插，头始终不是NULL
			tail->next = list2;
			tail = tail->next;
			list2 = list2->next;
		}
		else
		{
			tail->next = list1;
			tail = tail->next;
			list1 = list1->next;
		}
	}

	//当只有list2 为空的时候，后面的只需继承list1即可 tail也不需要变化了。
	if (list1)
	{
		tail->next = list1;
	}
	//同理
	if (list2)
	{
		tail->next = list2;
	}

	//现在把虚拟节点释放掉即可
	struct ListNode* list = head->next;
	free(head);
	head = NULL;
	return list;
}



//判断其是否为回文链表 即是否对称： 奇数 1 2 3 2 1  偶数 1 2 2 1
//只需要找到中间节点 然后将后半部分逆置 然后从头比较和从中间往后比较即可
//bool isPalindrome(struct ListNode* head) {
	//struct ListNode* mid = middleNode(head);
	//struct ListNode* rhead = reverseList(mid);
	//while (rhead && head)
	//{
	//	if (head->val != rhead->val)
	//	{
	//		return false;
	//	}
	//	rhead = rhead->next;
	//	head = head->next;
	//}
	//return true;
//}

//链表分割
//给定一个x，比x小的排到x之前 比x大的排在x之后 x不排哦 4 2 7 6 1   x = 5    4 2 1  7 6
//法一 不带哨兵位
//struct ListNode* partition(struct ListNode* pHead, int x) {
//	if (pHead == NULL)
//	{
//		return NULL;
//	}
//	struct ListNode* greaterhead, * greatertail, * lesshead, * lesstail;
//	//没有带哨兵位的节点
//	greaterhead = greatertail = NULL;
//	lesshead = lesstail = NULL;
//
//	struct ListNode* pH = pHead;
//	while (pH)
//	{
//		if (x > pH->val)
//		{
//			if (lesshead == NULL)
//				lesshead = lesstail = pH;
//			else
//			{
//				lesstail->next = pH;
//				lesstail = lesstail->next;
//			}
//
//		}
//		else if (x <= pH->val)
//		{
//			if (greaterhead == NULL)
//				greaterhead = greatertail = pH;
//			else
//			{
//				greatertail->next = pH;
//				greatertail = greatertail->next;
//			}
//
//		}
//		pH = pH->next;
//	}
//	if (lesstail)//防止出现全大情况出现空指针引用
//		lesstail->next = greaterhead;
//	if (greatertail)//防止全小出现空指针引用
//		greatertail->next = NULL;
//	if (lesshead)
//		return lesshead;//全小或者普通情况
//	if (greaterhead)
//		return greaterhead;//全大情况
//}

//法二 带哨兵位
struct ListNode* partition(struct ListNode* pHead, int x) {
	struct ListNode* greaterhead, * greatertail, * lesshead, * lesstail;
	greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
	lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
	assert(greatertail && lesstail);//断言
	greatertail->next = NULL;
	lesstail->next = NULL;

	struct ListNode* pH = pHead;
	while (pH)
	{
		if (x > pH->val)
		{
			lesstail->next = pH;
			lesstail = lesstail->next;

		}
		else if (x <= pH->val)
		{
			greatertail->next = pH;
			greatertail = greatertail->next;

		}
		pH = pH->next;
	}

	lesstail->next = greaterhead->next;
	greatertail->next = NULL;// 管你最后是否为空均置为空，防止出现环
	struct ListNode* head = lesshead->next;
	free(lesshead);
	lesshead = NULL;
	return head;
}

//相交链表 即 两个链表最终变成了一个链表 求返回第一个相同的节点的地址 那么我们只需要依次比较地址，
//第一个地址相同即可，但是如果直接暴力比较的话，时间复杂度为O(n^2)为了让时间复杂度变成n我们遍历两个链表，把长的先走相差步数，那么两个链表长度相等就可以同步走了
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
	int lenA = 1;
	int lenB = 1;
	struct ListNode* curA, * curB;
	curA = headA;
	curB = headB;
	while (curA->next)
	{
		lenA++;
		curA = curA->next;
	}
	while (curB->next)
	{
		lenB++;
		curB = curB->next;
	}
	if (curA != curB)
	{
		return NULL;
	}
	struct ListNode* shortList = headA, * longList = headB;
	if (lenA > lenB)
	{
		shortList = headB;
		longList = headA;
	}
	int gap = abs(lenA - lenB);
	while (gap--)
	{
		longList = longList->next;
	}
	while (longList != shortList)
	{
		longList = longList->next;
		shortList = shortList->next;
	}
	return longList;
}
//环形链表 判断链表里面是否有环 用龟兔赛跑来解释：一个指针是另一个的二倍，当快的追上慢的是不是可以判定其为有环呢？
//bool hasCycle(struct ListNode* head) {
//	struct ListNode* slow, * fast;
//	slow = fast = head;
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//		if (fast == slow)
//		{
//			return true;
//		}
//	}
//	return false;
//}

//如果是带环链表 返回环的第一个节点位置 
//首先利用快慢指针一个前进1一个前进2当他们在开始后记录第一次相遇的位置，然后从该位置开始和从头位置两指针开始移动 他们相遇就是这第一个节点了。
struct ListNode* detectCycle(struct ListNode* head) {

	//首先定义快慢指针 找到它们的相遇点
	struct ListNode* slow, * fast;
	slow = fast = head;//同一起点

	//循环开始
	while (fast && fast->next)
	{
		slow = slow->next;//移动一步
		fast = fast->next->next;//移动两步

		if (slow == fast)//两者地址相等 记录节点开始下次循环
		{
			struct ListNode* meet = fast;
			
			//一个从头开始，一个从这里开始
			while (meet != head)
			{
				meet = meet->next;
				head = head->next;
			}
			return meet;
		}
	}

	return NULL;
}

int main()
{
	SLNode* s1 = (SLNode*)malloc(sizeof(SLNode));
	assert(s1);
	SLNode* s2 = (SLNode*)malloc(sizeof(SLNode));
	assert(s2);
	SLNode* s3 = (SLNode*)malloc(sizeof(SLNode));
	assert(s3);

	SLNode* a1 = (SLNode*)malloc(sizeof(SLNode));
	assert(a1);
	SLNode* a2 = (SLNode*)malloc(sizeof(SLNode));
	assert(a2);


	s1->val = 4;
	s1->next = s2;

	s2->val = 2;
	s2->next = s3;

	s3->val = 7;
	s3->next = a1;

	a1->val = 6;
	a1->next = a2;

	a2->val = 1;
	a2->next = NULL;
	

	SListPrint(s1);
	SListPrint(partition(s1, 5));
	return 0;
}


//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
//
//例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//
//返回复制链表的头节点。
//
//用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个 [val, random_index] 表示：
//
//val：一个表示 Node.val 的整数。
//random_index：随机指针指向的节点索引（范围从 0 到 n - 1）；如果不指向任何节点，则为  null 。
//你的代码 只 接受原链表的头节点 head 作为传入参数。
//

/*
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
	//1 创建新的节点 只修改next 在对应节点后复制一个
	while (cur)
	{
		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));

		copy->val = cur->val;
		copy->next = cur->next;
		cur->next = copy;
		copy->random = NULL;
		cur = copy->next;
	}

	cur = head;
	//2修改random中的值
	while (cur)
	{
		struct Node* copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
			copy->random = cur->random->next;
		cur = copy->next;
	}
	//3将复制的新链表分离出来
	cur = head;
	struct Node* copyhead, * copytop;
	copyhead = copytop = NULL;
	while (cur)
	{
		struct Node* copy = cur->next;
		struct Node* next = copy->next;
		if (!copyhead)
		{
			copyhead = copytop = copy;
		}
		else
		{
			copytop->next = copy;
			copytop = copy;
		}
		cur->next = next;
		cur = next;
	}
	return copyhead;
}*/
